﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace DiffCons//差分约束
{
	TEST_CLASS(P5960)
	{
		//【差分约束】P5960 差分约束|普及+		
		class Solution {
		public:
			vector<int> Ans(int N,vector<tuple<int,int,int>> edge) {
				for (auto& [v, u, w] : edge) {
					swap(u, v);
				}
				for (int i = 1; i <= N; i++) {
					edge.emplace_back(0, i, 0);
				}
				CDisNegativeRing<> dis;
				if (!dis.Dis(N + 1, edge, 0)) { return {}; }
				
				return vector<int>(dis.m_vDis.begin()+1,dis.m_vDis.end());
			}
		};
	public:
		void Check(const vector<tuple<int, int, int>>& edge,const vector<int>& res) {
			for (const auto& [x1, x2, y] : edge) {
				Assert::IsTrue(res[x1 - 1] - res[x2 - 1] <= y);
			}
		}
		TEST_METHOD(TestMethod1)
		{
			vector<tuple<int, int, int>> edge = { {1,2,3},{2,3,-2},{1,3,1} };
			auto res = Solution().Ans(3,edge);
			Check(edge, res);
		}
		TEST_METHOD(TestMethod12)
		{
			vector<tuple<int, int, int>> edge = { {1,2,1} };
			auto res = Solution().Ans(2, edge);
			AssertEx({ 0,0 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			vector<tuple<int, int, int>> edge = { {1,2,-1} };
			auto res = Solution().Ans(2, edge);
			AssertEx({ -1,0 }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			vector<tuple<int, int, int>> edge = { {1,2,-1},{2,3,-2},{3,1,-2} };
			auto res = Solution().Ans(4, edge);
			Assert::IsTrue(0 == res.size());
		}
	};

	TEST_CLASS(P4878)
	{
		//【差分约束】P4878 [USACO05DEC] Layout G|普及+	
		class Solution {
		public:
			int Ans(int N, const vector<tuple<int, int, int>> edge1, const vector<tuple<int, int, int>> edge2) {
				vector<tuple<int, int, int>> edge;
				for (auto& [a, b, d] : edge1) {
					edge.emplace_back(a, b, d);
				}
				for (auto& [a, b, d] : edge2) {
					edge.emplace_back(b, a, -d);
				}
				for (int i = 1; i <= N; i++) {
					edge.emplace_back(0, i, INT_MAX/2);
					edge.emplace_back(i, 0, INT_MAX / 2);
				}
				for (int i = 1; i < N; i++) {
					edge.emplace_back(i + 1, i, -1);
				}
				CDisNegativeRing<long long,LLONG_MAX/2> dis;
				if (!dis.Dis(N + 1, edge, 1)) { return -1; }
				if (dis.m_vDis[N] > INT_MAX / 2) { return -2; }
				return dis.m_vDis[N]-dis.m_vDis[1];
			}
		};
	public:	
		int n;
		vector<tuple<int, int, int>> edge1, edge2;
		TEST_METHOD(TestMethod1)
		{
			n = 4,  edge1 = { {1,3,10},{2,4,20} }, edge2 = { {2,3,3} };	
			auto res = Solution().Ans(n,edge1,edge2);
			AssertEx(27, res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = 3, edge1 = { {1,3,1} }, edge2 = { {1,2,1},{2,3,1} };	
			auto res = Solution().Ans(n, edge1, edge2);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod3)
		{
			n = 3, edge1 = { {1,2,1} }, edge2 = { };
			auto res = Solution().Ans(n, edge1, edge2);
			AssertEx(-2, res);
		}
		TEST_METHOD(TestMethod4)
		{
			n = 4, edge1 = { {1,4,10} }, edge2 = { {2,3,20} };
			auto res = Solution().Ans(n, edge1, edge2);
			AssertEx(-1, res);
		}
	};

	TEST_CLASS(P3275)
	{
		//【差分约束】 P3275 [SCOI2011] 糖果|省选-	
		class CMyTopSort
		{
		public:
			//入度为0的是叶子节点
			long long TopSort(const int N, const vector<tuple<int, int, int>>& edge, CUnionFind& uf) {
				m_vDis.assign(N, 1);
				m_vDis[0] = 1;
				vector<int> out(N);
				vector<vector<pair<int, int>>> neiBoBack(N);
				for (const auto& [u, v, w] : edge) {
					const int v1 = uf.GetConnectRegionIndex(v);
					const int u1 = uf.GetConnectRegionIndex(u);
					if (u1 == v1) { continue; }
					neiBoBack[v1].emplace_back(u1, -w);
					out[u1]++;
				}
				queue<int> que;
				for (int i = 1; i < N; i++) {
					if (0 == out[i]) {
						if (i != uf.GetConnectRegionIndex(i)) { continue; }
						que.emplace(i);
						m_vDis[i] = 1;
					}
				}
				while (que.size()) {
					const auto cur = que.front();
					que.pop();
					for (const auto& [next, w] : neiBoBack[cur]) {
						m_vDis[next] = max(m_vDis[next], m_vDis[cur] + w);
						if (0 == --out[next]) {
							que.emplace(next);
						}
					}
				}
				long long ans = 0;
				vector<int> tmp = { 1 };
				for (int i = 1; i < N; i++) {
					ans += m_vDis[uf.GetConnectRegionIndex(i)];
					tmp.emplace_back(m_vDis[uf.GetConnectRegionIndex(i)]);
				}
				return ans;
			}
			vector<int> m_vDis;
		};
		class Solution {
		public:
			long long Ans(int N, const vector<tuple<int, int, int>> ope) {
				vector<tuple<int, int, int>> edge;
				for (const auto& [x, a, b] : ope) {
					if (1 == x) {//x=1,即 A-B <=0 B - A <=0
						edge.emplace_back(a, b, 0);
						edge.emplace_back(b, a, 0);
					}
					else if (2 == x) {//x = 2 A - B < 0 即 A - B <= -1
						edge.emplace_back(b, a, -1);
					}
					else if (3 == x) {//x=3 A-B >=0 即 B-A <=0
						edge.emplace_back(a, b, 0);
					}
					else if (4 == x) {//x=4 A-B >0 即B-A<0 即B-A<=-1
						edge.emplace_back(a, b, -1);
					}
					else if (5 == x) {//x = 5即 A - B <= 0
						edge.emplace_back(b, a, 0);
					}
				}
				for (int i = 1; i <= N; i++) {
					edge.emplace_back(0, i, 0);
				}
				vector<vector<pair<int, int>>> neiBo(N + 1);
				for (const auto& [u, v, w] : edge) {
					neiBo[u].emplace_back(v, w);
				}
				CUnionFind uf(N + 1);
				{
					vector<bool> vis(N + 1);
					bool bErr = false;
					function<void(vector<int>&, vector<int>&, int, int)> DFS = [&](vector<int>& pars, vector<int>& pw, int w, int cur) {
						if (vis[cur]) { return; }
						if (1 != pw[cur]) {//找到环
							if (0 != w - pw[cur]) { bErr = true; return; }
							for (int i = pars.size() - 1; pars[i] != cur; i--) {
								uf.Union(cur, pars[i]);
							}
							return;
						}
						pars.emplace_back(cur);
						pw[cur] = w;
						for (const auto& [next, ew] : neiBo[cur]) {
							DFS(pars, pw, w + ew, next);
						}
						pw[cur] = 1;
						pars.pop_back();
						vis[cur] = true;
					};
					vector<int> pars, pw(N + 1, 1);
					DFS(pars, pw, 0, 0);
					if (bErr) { return -1; }
				}
				return CMyTopSort().TopSort(N + 1, edge, uf);
			}
		};
	public:
		int n;
		vector<tuple<int, int, int>> ope;
		TEST_METHOD(TestMethod1)
		{
			n = 5, ope = { {1,1,2},{2,3,2},{4,4,1},{3,4,5},{5,4,5},{2,3,5},{4,5,1} };
			auto res = Solution().Ans(n, ope);
			AssertEx(11LL, res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = 4, ope = { {1,3,2},{2,2,4},{5,1,3},{3,4,2},{3,2,3},{4,3,1},{5,1,4} };
			auto res = Solution().Ans(n, ope);
			AssertEx(8LL, res);
		}
		TEST_METHOD(TestMethod3)
		{
			n = 100000, ope.resize(n-1);
			for (int i = 1; i < n; i++) {
				ope[i - 1] = { 2,i,i + 1 };
			}
			auto res = Solution().Ans(n, ope);
			AssertEx(5000050000LL, res);
		}
		TEST_METHOD(TestMethod4)
		{
			n = 700, ope.resize(n - 1);
			for (int i = 1; i < n; i++) {
				ope[i - 1] = { 1,i,i + 1 };
			}
			auto res = Solution().Ans(n, ope);
			AssertEx((long long)n, res);
		}
		TEST_METHOD(TestMethod5)
		{
			n = 100000, ope = {};
			auto res = Solution().Ans(n, ope);
			AssertEx((long long)n, res);
		}
		TEST_METHOD(TestMethod6)
		{
			n = 4, ope = { {2,1,2},{2,2,3},{2,1,4} };
			auto res = Solution().Ans(n, ope);
			AssertEx((long long)8, res);
		}
	};

	TEST_CLASS(P5590)
	{
		//【差分约束】P5590 赛车游戏|省选-
		class Solution {
		public:
			vector<int> Ans(int N, const vector<pair<int, int>>& edge) {
				auto neiBo = CNeiBo::Two(N, edge, true, 1);
				vector<vector<int>> neiBoBack(N);
				for (int i = 0; i < N; i++) {
					for (const auto& j : neiBo[i]) {
						neiBoBack[j].emplace_back(i);
					}
				}
				CBFSDis dis1(neiBo, { 0 });
				if (dis1.m_iNotMayDis == dis1.m_vDis.back()) { return {}; }
				CBFSDis dis2(neiBoBack, { N - 1 });
				vector<tuple<int, int, int>> edge2;
				auto Not = [&](int i, int j) {
					if ((dis1.m_vDis[i] > N) || (dis1.m_vDis[j] > N)) { return true; }
					if ((dis2.m_vDis[i] > N) || (dis2.m_vDis[j] > N)) { return true; }
					return false;
				};
				for (auto [i, j] : edge) {
					i--, j--;
					if (Not(i,j)) { continue; }
					//eves[i] < leves[j] ,即levevs[i] -leves[j] <=-1,leves[j]-leves[i] <=9。由于levevs[i] -leves[j]<=-1,
					edge2.emplace_back(j, i, -1);
					edge2.emplace_back(i, j, 9);
				}
				CDisNegativeRing dis;
				if (!dis.Dis(N, edge2, 0)) { return {}; }
				vector<int> ans;
				for (auto [i, j] : edge) {
					i--, j--;
					if (Not(i, j)) { ans.emplace_back(9); continue; }
					ans.emplace_back(dis.m_vDis[j] - dis.m_vDis[i]);
				}
				return ans;
			}
		};
	public:
		int n;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod1)
		{
			n = 3, edge = { {1,2} };
			auto res = Solution().Ans(n, edge);
			AssertV({}, res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = 10,edge = { {1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{9,10},{1,10} };
			auto res = Solution().Ans(n, edge);
			vector<int >act(edge.size(), 1);
			act.back() = 9;
			AssertV(act, res);
		}
		TEST_METHOD(TestMethod3)
		{
			n = 3, edge = { {1,3},{1,2} };
			auto res = Solution().Ans(n, edge);
			AssertV({9,9}, res);
		}
	};

	TEST_CLASS(P6696)
	{
		//【DFS 数学】P6696 [BalticOI 2020] 图 (Day2)|普及+
		class Solution {
		public:
			vector<float> Ans(int N, const vector<tuple<int, int, int>>& edge) {
				m_iN = N;
				m_neiBo = CNeiBo::Three(N, edge, false, 1);
				m_vk.assign(N, -100); m_vb.assign(N, 0);
				for (int i = 0; i < N; i++)
				{
					if (-100 != m_vk[i]) { continue; }				
					BFS(i);
				}
				if (!Check(m_vb, edge)) { return {}; }
				return m_vb;
			}
			void BFS(int root) {
				vector<int> que; vector<bool> vis(m_iN);
				vector<float> bs;
				que.emplace_back(root); vis[root] = true; m_vk[root] = 1;
				float x = 2e10;
				for(int i=0;i < que.size();i++) {
					const auto cur = que[i];					
					for (const auto& [next, w] : m_neiBo[cur]) {
						const auto k1 = -m_vk[cur];
						const auto b1 = w - m_vb[cur];
						if (-100 == m_vk[next]) {
							m_vk[next] = k1; m_vb[next] = b1;
						}
						else if ((x > 1e10) && (m_vk[next] != k1)) {
							x = (m_vb[next] - b1) / (k1 - m_vk[next]);
						}
						if (!vis[next]) {
							vis[next] = true; que.emplace_back(next);
						}
					}
				}
				if(x > 1e10)
				{
					for (const auto& cur : que) {
						if (1 == m_vk[cur]) {
							bs.emplace_back(-m_vb[cur]);
						}
						else if (-1 == m_vk[cur]) {
							bs.emplace_back(m_vb[cur]);
						}
					}
					if (bs.size()) {
						nth_element(bs.begin(), bs.begin() + bs.size() / 2, bs.end());
						x = bs[bs.size() / 2];
					}
				}						
				for (const auto& cur : que) {
					m_vb[cur] += m_vk[cur] * x;
				}
			}
			static bool Check(vector<float>& res,   vector<tuple<int, int, int>> edge) {
				for (auto [u, v, w] : edge) {
					u--, v--;
					if (abs(res[u] + res[v] - w) > 0.00001) { return false; }
				}
				return true;
			}
			int m_iN;
			vector<int> m_vk;
			vector<float> m_vb;
			vector<vector<std::pair<int, int>>> m_neiBo;
		};
	public:
		void Check(vector<float>& res ,float sum, const vector<tuple<int, int, int>>& edge) {
			float actsum = 0;
			for (const auto& f : res) {
				actsum += abs(f);
			}
			Assert::IsTrue(abs(actsum - sum) < 0.00001);
			Assert::IsTrue(Solution::Check(res, edge));
		}
		int N;
		vector<tuple<int, int, int>> edge;
		TEST_METHOD(TestMethod1)
		{
			N = 4, edge = { {1,2,1},{2,3,2},{1,3,2},{3,4,1} };
			auto res = Solution().Ans(N, edge);
			Check(res, 3, edge);
		}
		TEST_METHOD(TestMethod2)
		{
			N = 2, edge = { {1,2,1} };
			auto res = Solution().Ans(N, edge);
			Check(res, 1, edge);
		}
		TEST_METHOD(TestMethod3)
		{
			N = 3, edge = { {1,2,2},{2,3,2} };
			auto res = Solution().Ans(N, edge);
			Check(res, 2, edge);
		}
		TEST_METHOD(TestMethod4)
		{
			N = 3, edge = { {1,2,2},{2,2,1},{2,1,1},{1,2,2} };
			auto res = Solution().Ans(N, edge);
			AssertEx(0u, res.size());
		}
	};

	TEST_CLASS(P7150)
	{
		//【拓扑排序】P7150 [USACO20DEC] Stuck in a Rut S|普及+
		class Solution {
		public:
			vector<int> Ans(int N, const vector<tuple<char, int, int>>& cr) {				
				vector<tuple<int, int, int, int>> crCurPar;				
				auto Do = [&](int i, int j) {
					if (get<0>(cr[i]) == get<0>(cr[j])) { return; }
					if ('N' == get<0>(cr[i])) {
						swap(i, j);
					}
					const auto& [d1, c1, r1] = cr[i];
					const auto& [d2, c2, r2] = cr[j];
					if ((c1 > c2) || (r1 < r2)) { return; }
					int iCmp = (c2 - c1) - (r1 - r2);
					if (iCmp < 0) {
						crCurPar.emplace_back(c2,r1,j,i);
					}
					else if(iCmp >0 ){
						crCurPar.emplace_back(c2,r1,i, j);
					}
				};
				for (int i =0;i <N ;i++)for (int j = i+1;j < N ;j++ )
				{
					Do(i, j);
				}
				sort(crCurPar.begin(), crCurPar.end());
				vector<int> pars(N, -1);
				unordered_map<int, int> rToMaxC, cToMaxR;
				for (const auto& [c, r, cur, par] : crCurPar) {
					if (rToMaxC.count(r) && (rToMaxC[r] < c)){continue; }
					if (cToMaxR.count(c) && (cToMaxR[c] < r)) { continue; }
					pars[cur] = par;
					if ('N' == get<0>(cr[cur])) {
						cToMaxR[get<1>(cr[cur])] = r;
					}
					else {
						rToMaxC[get<2>(cr[cur])] = c;
					}
				}				
				CParentToNeiBo pn(pars);
				auto leves = CBFSLeve::Leve(pn.m_vChild, pn.m_roots);
				auto sort = CBFSLeve::LeveSort(leves);
				vector<int> e(N);
				for (auto it = sort.rbegin(); it != sort.rend(); ++it) {
					for (const auto& son : pn.m_vChild[*it]) {
						e[*it] += e[son] + 1;
					}
				}
				return e;
			}
		};
	public:
		int N;
		vector<tuple<char, int, int>> cr;
		TEST_METHOD(TestMethod1)
		{
			//在这个样例中，奶牛 3 阻碍了奶牛 2，奶牛 4 阻碍了奶牛 5，奶牛 5 阻碍了奶牛 6。根据传递性，奶牛 4 也阻碍了奶牛 6。
			N = 6, cr = { {'E',3,5},{'N',5,3},{'E',4,6},{'E',10,4},{'N',11,1},{'E',9,2} };
			auto res = Solution().Ans(N, cr);
			AssertV({0,0,1,2,1,0}, res);
		}

	};
}
